Fiat-Shamir協定

以上的洞穴模型只能當作ZKP的入門概念而已，那麼實際該如何將ZKP發揮出來呢？

Fiat-Shamir協定利用在mod(N=pq)中開根號很難這件事來設計ZKP(其複雜度與質因數分解相同)

數字N=pq是一個公開資訊，p和q都是質數(不公開)
Alice知道一個秘密S，該秘密的平方 也是公開

Alice必須說服Bob她知道S，但是不會洩漏任何S的資訊

該協定如下

1. Alice 隨機選一個數字r，計算 ，並寄送給Bob
2. Bob 隨機選擇e=數字0或1，並將e寄給Alice
3. Alice計算 ，最後將y傳給Bob
4. Bob只需驗證 即可

如果大家都有按照協定走，最後一條式子會是對的，因為

那麼至於這個協定能否讓不知道S的Trudy騙過Bob呢？

同樣Trudy先產生r，計算x後，傳給Bob
Bob將寄送挑戰e回來

1. 假設Trudy知道Bob寄來的e一定是0，他可以直接將他第一步生成的r在第三步回傳，如此通過認證
2. 假如Trudy知道Bob寄來的e一定是1，他可以在第一步的x動手腳，傳送假的 並在第三步傳送r回去
   注意到Bob 一樣可以驗證通過Trudy的解答

這裡的關鍵在於，Bob每次的挑戰e都要是隨機，如此Trudy的這套把戲再怎麼厲害，也敵不過機率的考驗
會發現一定要是懂S的人，才可以每次都通過認證